package leetcode.editor.cn;

import java.util.Arrays;

public class BaShuZuPaiChengZuiXiaoDeShu {
    public String minNumber(int[] nums) {
        String[] strNums = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strNums[i] = String.valueOf(nums[i]);
        }
        quickSort(strNums, 0 , nums.length - 1);
        StringBuffer res = new StringBuffer();
        for (String str : strNums) {
            res.append(str);
        }
        return res.toString();
    }

    void quickSort(String[] strNums, int l, int r) {
        if (l >= r) return;
        int i = l, j = r;
        String key = strNums[l];
        while (i < j) {
            while (i < j && (key + strNums[j]).compareTo(strNums[j] + key) <= 0) j--;
            while (i < j && (key + strNums[i]).compareTo(strNums[i] + key) >= 0) i++;
            swap(strNums, i , j);
        }
        swap(strNums, l , i);
        quickSort(strNums, l, i - 1);
        quickSort(strNums, i + 1, r);
    }

    void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {3, 30, 34, 5, 9};
        System.out.println(new BaShuZuPaiChengZuiXiaoDeShu().minNumber(nums));
    }
}
